package dataStructures.impl;

import dataStructures.IPriorityQueue;

/**
 * Maximum priority queue implementation of {@link IPriorityQueue}
 * 
 * @author Vikas Bahirwani
 */
public class MaxPriorityQueue implements IPriorityQueue {

	MaxHeap maxHeap;
	int capacity;

	public MaxPriorityQueue(int capacity) {
		maxHeap = new MaxHeap(new int[capacity]);
		this.capacity = capacity;
	}

	@Override
	public void insert(int key) {
		int heapSize = maxHeap.getHeapSize();
		if (heapSize + 1 == capacity) {
			throw new RuntimeException("Priority Queue full");
		}

		maxHeap.setHeapSize(heapSize + 1);
		int[] elements = maxHeap.getElements();
		elements[heapSize + 1] = Integer.MIN_VALUE;
		updatePriority(heapSize + 1, key);
	}

	@Override
	public void updatePriority(int keyIndex, int newPriority) {
		if (keyIndex >= 0 && keyIndex <= maxHeap.getHeapSize()) {
			int[] elements = maxHeap.getElements();
			if (elements[keyIndex] > newPriority) {
				throw new RuntimeException(
						"New priority cannot be less than existing priority");
			}

			elements[keyIndex] = newPriority;
			while (keyIndex > 0
					&& (elements[maxHeap.getParent(keyIndex)] < elements[keyIndex])) {
				int temp = elements[keyIndex];
				elements[keyIndex] = elements[maxHeap.getParent(keyIndex)];
				elements[maxHeap.getParent(keyIndex)] = temp;
				keyIndex = maxHeap.getParent(keyIndex);
			}
		} else {
			throw new RuntimeException("keyIndex out of bounds");
		}

	}

	@Override
	public int getHighestPriority() {
		if (maxHeap.getHeapSize() < 0) {
			throw new RuntimeException(
					"There are no elements in the priority queue");
		}
		return maxHeap.getElements()[0];
	}

	@Override
	public int extractHighestPriority() {
		if (maxHeap.getHeapSize() < 0) {
			throw new RuntimeException(
					"There are no elements in the priority queue");
		}
		int[] elements = maxHeap.getElements();
		int maxPriority = elements[0];
		elements[0] = elements[maxHeap.getHeapSize()];
		maxHeap.setHeapSize(maxHeap.getHeapSize() - 1);
		maxHeap.heapify(0);
		return maxPriority;

	}

	public static void main(String[] args) {
		IPriorityQueue priorityQueue = new MaxPriorityQueue(10);
		try {
			priorityQueue.getHighestPriority();
		} catch (RuntimeException e) {
			System.out.println(e.getMessage());
		}

		try {
			priorityQueue.extractHighestPriority();
		} catch (RuntimeException e) {
			System.out.println(e.getMessage());
		}
		priorityQueue.insert(7);
		priorityQueue.insert(3);
		priorityQueue.insert(2);
		priorityQueue.insert(6);
		priorityQueue.insert(9);
		priorityQueue.insert(15);
		priorityQueue.insert(12);

		try {
			priorityQueue.updatePriority(7, 10);
		} catch (RuntimeException e) {
			System.out.println(e.getMessage());
		}

		try {
			priorityQueue.updatePriority(4, -1);
		} catch (RuntimeException e) {
			System.out.println(e.getMessage());
		}

		try {
			priorityQueue.updatePriority(4, 10);
		} catch (RuntimeException e) {
			System.out.println(e.getMessage());
		}

		System.out.println(priorityQueue.getHighestPriority());

		while (true) {
			System.out.println(priorityQueue.extractHighestPriority());
		}
	}

}
